#include <stdio.h>
#include <vector>

using namespace std;

#define SIZE(a) (sizeof(a) / sizeof(a[0]))

void find_next(vector<vector<int> > &data, vector<vector<int> > &result, int layer, vector<int> cur_list);
void find_all(vector<vector<int> > &data, vector<vector<int> > &result);
void show(vector<vector<int> > &result);

int main()
{
    vector<vector<int> > data;
    vector<vector<int> > result;

    int a1[] = { 1 };
    int a2[] = { 2 };
    int a3[] = { 7, 3, 8 };
    int a4[] = { 6, 9, 4, 10 };
    int a5[] = { 11, 5 };
    data.push_back(vector<int>(a1, a1 + SIZE(a1)));
    data.push_back(vector<int>(a2, a2 + SIZE(a2)));
    data.push_back(vector<int>(a3, a3 + SIZE(a3)));
    data.push_back(vector<int>(a4, a4 + SIZE(a4)));
    data.push_back(vector<int>(a5, a5 + SIZE(a5)));

    // 递归
    vector<int> curlist;
    find_next(data, result, 0, curlist);
    show(result);

    // 循环
    result.clear();
    find_all(data, result); 
    show(result);
      
    return 0;
}

void show(vector<vector<int> > &result)
{
    int index = 0;
    printf("\n");
    for (int i = 0; i < (int)result.size(); i++)
    {
        printf("%2d->", index++);
        for (int k = 0; k < (int)result[i].size(); k++)
        {
            printf("%2d ", result[i][k]);
        }
        printf("\n");
    }
}

// 笛卡尔积的两种方法
// 1. 递归
void find_next(vector<vector<int> > &data, vector<vector<int> > &result, int layer, vector<int> cur_list)
{
    if (layer == data.size())
    {
        result.push_back(cur_list);
        return;
    }

    for (int i = 0; i < (int)data[layer].size(); i++)
    {
        vector<int> list(cur_list);
        list.push_back(data[layer][i]);
        find_next(data, result, layer + 1, list);
    }
}

// 2. 循环
void find_all(vector<vector<int> > &data, vector<vector<int> > &result)
{
    int total_num = 1;
    vector<int> layer;
    for (int i = (int)data.size() - 1; i >= 0; i--)
    {              
        layer.insert(layer.begin(), total_num);
        total_num *= data[i].size();
    }   

    for (int i = 0; i < total_num; i++)
    {
        int index = i;
        vector<int> list;
        for (int k = 0; k < (int)data.size(); k++)
        {
            int layer_index = index / layer[k];
            list.push_back(data[k][layer_index]);
            index %= layer[k];
        }
        result.push_back(list);
    }
}
